package org.zxp.algorithm.search;

import org.zxp.algorithm.sort.QuickSort;

/**
 * @program: effectiveJava
 * @description: 二分查找实现
 * @author: X-Pacific zhang
 * @create: 2019-07-29 14:43
 **/
public class BinarySearch {
    static int findTimes = 0;
    public static void main(String[] args) {
        int[] sorts = {4, 5, 3, 2, 7, 9, 2, 5};
        QuickSort.quick_sort(sorts, 0, sorts.length - 1);

//        int result = b_find_rec(sorts,0,sorts.length-1, 7);
        int result = b_find_loop(sorts,7);
        System.out.println("查找结果："+result);
        System.out.println("查找次数："+findTimes);
    }

    /**
     * 二分查找的递归实现
     * @param a
     * @param begin
     * @param end
     * @param x
     * @return
     */
    public static int b_find_rec(int[] a,int begin,int end,int x){
        findTimes++;
        if(begin > end){
            return -1;
        }
        int mid = (begin+end)/2;
        //如果怕begin+end溢出，则可以用：begin+(end-begin)/2
        if(a[mid] == x){
            return mid;
        }
        else if(x > a[mid]){
            return b_find_rec(a, mid+1, end, x);
        }else{
            return b_find_rec(a, begin, mid-1, x);
        }
    }

    /**
     * 二分查找的循环实现
     * @param a
     * @param x
     * @return
     */
    public static int b_find_loop(int[] a,int x){
        int begin = 0;
        int end = a.length - 1;
        while(begin <= end){
            findTimes++;
            int mid = (begin + end)/2;
            if(a[mid] == x){
                return mid;
            }else if(x > a[mid]){
                begin = mid + 1;
                continue;
            }else{
                end = mid - 1;
                continue;
            }
        }
        return  -1;
    }
}
